package javaguide.algorithm;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

@Slf4j
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 4, 7, 9, 1, 2, 6, 8};
        shellSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        int n = arr.length;
        int gap = n / 2;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int current = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = current;
            }
            log.info("======arr:{}", Arrays.toString(arr));
            gap /= 2;
        }
    }
}
